package 快速排序;

import java.util.*;

/**
 *快速排序的主要思想就是分而治之
 *
 *
 * Created by sult on 2018/8/2.
 */
public class Demo {





    public  int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
    {
        int i = l, j = r;
        int x = s[l]; //s[l]即s[i]就是第一个坑
        while (i < j)
        {
            // 从右向左找小于x的数来填s[i]
            while(i < j && s[j] >= x)
                j--;
            if(i < j)
            {
                s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
                i++;
            }

            // 从左向右找大于或等于x的数来填s[j]
            while(i < j && s[i] < x)
                i++;
            if(i < j)
            {
                s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
                j--;
            }
        }
        //退出时，i等于j。将x填到这个坑中。
        s[i] = x;

        return i;
    }

    public void quick_sort1(int s[], int l, int r)
    {
        if (l < r)
        {
            int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
            quick_sort1(s, l, i - 1); // 递归调用
            quick_sort1(s, i + 1, r);
        }
    }



    public static void main(String[] args) {
        Demo d = new Demo();
        int[] nums = {27, 31, 35, 50, 52, 58, 60, 62, 66, 68, 69, 1, 2, 5, 7, 9, 12, 20, 21, 23, 24};
        d.quick_sort1(nums,0,nums.length-1);
        for(int i:nums){
            System.out.print(i+",");
        }

    }


}

